7 Contenitori
7.1 Array
Ci sono due caratteristiche che distinguono gli array dagli altri tipi di contenitori: efficienza e tipo.
L’array è il modo più efficiente che Java fornisce per memorizzare ed accedere direttamente ad una sequenza di oggetti.
Il prezzo di questa efficienza è quello di avere una dimensione predefinita che non può essere modificata durante il proprio ciclo di vita.
Come alternativa, Java fornisce la classe ArrayList che però paga la maggiore flessibilità con la minore efficienza.
Rispetto ad un contenitore generico, l’array contiene un tipo specifico di oggetto.
E’ conveniente usare gli array quando si vuole guadagnare in termini di efficienza e controllo sul tipo di oggetti. Negli altri casi, infatti, potrebbero risultare un po’ restrittivi.
L’unico membro accessibile di un array è length che dice il numero di oggetti contenuti nell’array mentre la sintassi ‘[]’ è l’unico modo per accedere all’oggetto di un array.
Se si superano i confini specificati per una istanza di array, viene generata una IndexOutOfBoundException, una eccezione che estende RunTimeException, pertanto è una eccezione non controllata.
A differenza degli array, le classi contenitore possono contenere solo riferimenti ad oggetti.
Si aggira questo limite con le classi “wrapper” che permettono di inserire dei valori primitivi in un contenitore.
Tuttavia è più efficiente e semplice creare un array di tipi primitivi anziché un contenitore di classi “wrapper”.
7.1.1 Restituzione dell’array
In C/C++ non è possibile restituire un intero array ma solo un puntatore all’array (con tutti i problemi del caso dovuti al fenomeno di memory leak).
Java utilizza lo stesso approccio restituendo però un array di riferimenti agli oggetti senza alcuna preoccupazione sulla dimensione.
7.1.2 Arrays
Java include nella sua libreria java.util, la classe Arrays che contiene un insieme di metodi statici che supportano le funzioni di utilità per gli array. Non ci sono altri costruttori, quindi tutti i metodi definiti devono essere di classe per poter garantire l’utilizzabilità di Arrays.
Ci sono quattro funzioni di base:
equals(): confronta per uguaglianza due array;
fill(): riempie un array con un valore;
sort(): ordina un array;
binarySearch() : ritrova un elemento in array ordinato.
asList(): prende un array e inserisce i suoi elementi in un List.
Tutti questi metodi sono ‘overloaded’ per tutti i tipi primitivi e gli oggetti di classe Object.
7.1.3 Copia di un array
La libreria standard di Java fornisce un metodo static, System.arraycopy(), che effettua la copia di un array più velocemente del classico ciclo for.
Gli argomenti del metodo arraycopy() sono:
l’array sorgente;
l’indirizzo dell’array sorgente da cui iniziare la copia;
l’array di destinazione;
l’indirizzo dell’array di destinazione dove inizia la copia;
il numero di elementi da copiare.
Nel caso degli oggetti sono duplicati solo i riferimenti agli oggetti, non c’è alcuna duplicazione degli oggetti stessi (shallow copy). Per fare la deep copy si utilizza la clonazione.
import com.prova.util.*;
import java.util.*;
public class CopyingArrays {
public static void main(String[] args) {
int[] i = new int[25];
int[] j = new int[25];
Arrays.fill(i, 47); // i = {47, 47, 47, 47, ...}
Arrays.fill(j, 99);
System.arraycopy(i, 0, j, 0, i.length);
int[] k = new int[10];
Arrays.fill(k, 103);
System.arraycopy(i, 0, k, 0, k.length);
Arrays.fill(k, 103);
System.arraycopy(k, 0, i, 0, k.length);
Integer[] u = new Integer[10];
Integer[] v = new Integer[5];
Arrays.fill(u, new Integer(47));
Arrays.fill(v, new Integer(99));
System.arraycopy(v, 0, u, u.length/2, v.length);
}
}7.1.4 Confronto di array
La classe Arrays fornisce il metodo equals() ‘overloaded’ per tutti i tipi primitivi e per gli oggetti Object. Questo metodo confronta i corrispondenti elementi di due array e restituisce true se i due array sono uguali. Il confronto di uguaglianza per array di oggetti si basa sui contenuti (mediante Object.equals()). La classe Object implementa equals nel modo più restrittivo (x == y), ovvero confronta i riferimenti degli oggetti. Questo comportamento è stato sovrascritto da classi come String per confrontare i contenuti dei riferimenti.
import java.util.*;
public class ComparingArrays {
public static void main(String[] args) {
int[] a1 = new int[10];
int[] a2 = new int[10];
Arrays.fill(a1, 47);
Arrays.fill(a2, 47);
System.out.println(Arrays.equals(a1, a2));
a2[3] = 11;
System.out.println(Arrays.equals(a1, a2));
String[] s1 = new String[5];
Arrays.fill(s1, "Hi");
String[] s2 = {"Hi", "Hi", "Hi", "Hi", "Hi"};
System.out.println(Arrays.equals(s1, s2));
}
}
/*
Output
true
false
true
*/7.1.5 Comparazione degli elementi di un array
L’approccio di Java è basato sulla tecnica del callback, per cui la parte del codice che varia da caso a caso è incapsulata all’interno della rispettiva classe mentre la parte di codice che resta invariata richiamerà il codice che cambia.
Il primo è attraverso il metodo di confronto naturale che viene comunicato alla classe mediante la implementazione dell’interfaccia java.lang.Comparable. Questa semplice interfaccia è fornita di un singolo metodo:
public int compareTo(Object o);che prende un oggetto generico Object come argomento e restituisce un valore negativo se l’argomento è più piccolo dell’oggetto corrente, zero se è uguale e un valore positivo se è maggiore.
class Studente implements Comparable {
int matricola;
int numeroEsami;
String cognome;
String nome;
Studente(int matricola, int numeroEsami, String cognome, String nome) {
this.matricola = matricola;
this.numeroEsami = numeroEsami;
this.cognome = cognome;
this.nome = nome;
}
// il criterio in questo caso è il numeroEsami
public int compareTo(Object o) {
Studente s = (Studente) o;
if (s.numeroEsami == this.numeroEsami) {
return 0;
} else if (s.numeroEsami < this.numeroEsami) {
return -1;
} else {
return 1;
}
}
}Il secondo modo è quello di creare una classe che implementa l’interfaccia Comparator che ha due metodi:
public int compare(Object o1, Object o2)
public boolean equals(Object obj)Il metodo compare deve restituire un valore intero negativo, nullo o positivo a seconda del risultato del confronto.
class StudenteComp implements Comparator {
public int compare(Object o1, Object o2) {
Studente s1 = (Studente) o1;
Studente s2 = (Studente) o2;
return s1.cognome.compareTo(s2.cognome)
}
public boolean equals(Object o1) {
Studente s1 = (Studente) o1;
return s1.cognome.equals(s2.cognome);
}
}Se volessi invece ordinare gli studenti sulla base della matricola dovrei creare una nuova classe. Pertanto, per ogni criterio di ordinamento, è necessaria una classe nuova.
8 Comparator vs Comparable
Ora confrontiamo l’utilizzo delle due implementazioni:
Comparable: (Comparable)s1.compareTo((Comparable)s2)
Comparator: c.compare(s1, s2) dove c è un oggetto ComparatorL’implementazione con Comparator ci garantisce che a runtime non avremo problemi dato che non vi sono cast.
Se esiste un criterio d’ordine naturale questo viene implementato direttamente sulla classe utilizzando il Comparable. Gli altri criteri che vengono usati in maniera eccezionale vengono implementati come Comparator.
Vediamo come ad esempio funziona Arrays.sort() rispetto alle due interfacce.
Se voglio utilizzare il criterio di ordinamento naturale mi basterà chiamare Arrays.sort(T[] array), che utilizzerà il compareTo realizzato per gli oggetti presenti nell’array.
Se voglio utilizzare un qualsiasi altro criterio di ordinamento utilizzerò Arrays.sort(T[] array, Comparator c) passando un oggetto di tipo Comparator.
9 Contenitori
I contenitori di Java si basano su due distinti concetti:
Collection: un gruppo di singoli elementi a cui spesso sono applicati dei vincoli (e.g., un oggetto della classe List deve contenere elementi in una particolare sequenza, uno della classe Set non può contenere elementi duplicati).
Map: un gruppo di coppie “chiave - oggetto valore”
La distinzione tra le due categorie di contenitori in Java è quindi basata sul numero di elementi contenuti in ogni locazione del contenitore.
9.1 Collection
La categoria Collection contiene un elemento in ogni locazione. Essa include il tipo List che contiene un gruppo di elementi in una particolare sequenza e il tipo Set che permette solo l’aggiunta di un elemento di un dato tipo. L‘ArrayList è un tipo di List e HashSet è un tipo di Set.
Per aggiungere elementi a qualsiasi Collection si usa il metodo add().
Per quanto riguarda il riempimento di un contenitore, si può usare il metodo fill() anche se solo per il tipo List.
9.2 Map
I contenitori Map contengono coppie di chiave-valore.
Per aggiungere elementi ad un Map si usa il metodo put() che acquisisce in input una chiave ed un valore come argomenti.
Un contenitore Map può restituire:
un Set contenente tutte le sue chiavi,
una Collection contenente tutti i suoi valori,
un Set di coppie.
9.3 Visualizzare i contenitori
A differenza degli array, che consentono la stampa di un elemento alla volta in un ciclo for, i contenitori si possono visualizzare con facilità.
import java.util.*;
public class PrintingContainers {
static Collection fill(Collection c) {
c.add("dog");
c.add("dog");
c.add("cat");
return c;
}
static Map fill(Map m) {
m.put("dog", "Bosco");
m.put("dog", "Spot");
m.put("cat", "Rags");
return m;
}
public static void main(String[] args) {
System.out.println(fill(new ArrayList()));
System.out.println(fill(new HashSet()));
System.out.println(fill(new HashMap()));
}
}Per l’esempio precedente avremo il seguente output:
[dog, dog, cat] // Collection
[cat, dog] // Collection
{cat = Rags, dog = Spot} // Map9.4 Svantaggi dei contenitori
Quando si usano i contenitori Java si perde l’informazione relativa al tipo di oggetto che si inserisce in essi.
Ciò porta alle seguenti considerazioni:
non essendoci controllo sul tipo degli oggetti inclusi nel contenitore, non è possibile essere sicuri di avere dei contenitori di oggetti omogenei;
l’unica cosa che il contenitore conosce è che contiene dei riferimenti ad oggetti, pertanto è necessario effettuare un cast al tipo corretto prima di utilizzarli.
Se in un contenitore di riferimenti ad oggetti di tipo ‘cerchio’ si inserisce un oggetto di tipo ‘quadrato’, nel momento in cui si andranno a manipolare gli oggetti del contenitore trattandoli tutti come ‘cerchio’ verrà sollevata una ClassCastException.
L’identificazione al run-time del tipo è comunque possibile in Java (RTTI).
9.5 Iteratori
Un iteratore è un oggetto che si muove attraverso una sequenza di oggetti e ne seleziona uno qualsiasi senza che il programmatore sia a conoscenza della struttura sottostante della sequenza.
Ad ogni contenitore si può chiedere, mediante il metodo iterator(), di generare un opportuno iteratore, che altro non è che una istanza di una classe che implementa l’interfaccia Iterator.
L’interfaccia Iterator di Java permette di:
restituire il primo elemento della sequenza sulla prima chiamata del metodo next().
prendere l’oggetto successivo nella sequenza con l’invocazione del metodo next();
verificare se ci sono altri oggetti nella sequenza con hasNext();
rimuovere l’ultimo elemento restituito dall’iteratore con il metodo remove();
import java.util.*;
public class CatsAndDogs2 {
public static void main(String[] args) {
ArrayList cats = new ArrayList();
for(int i = 0; i < 7; i++) {
cats.add(new Cat(i));
}
}
Iterator e = cats.iterator();
while(e.hasNext()) {
((Cat)e.next()).print();
}
}9.6 For Each
Per tutte le classi che per le quali è definita l’operazione iterator() si può usare la struttura di controllo for-each.
Iterator<Cat> it = cats.iterator();
while(it.hasNext())
it.next().print();
// Equivalenti
for(Cat o: cats)
o.print();10 List
L’interfaccia List mantiene gli elementi nell’ordine in cui sono inseriti.
Una List produrrà un ListIterator che potrà spostarsi nella lista in entrambe le direzioni al suo interno.
Per specializzare il comportamento di List sono disponibili le sottoclassi:
ArrayList: List implementata con un array. Permette un accesso rapido agli elementi ma risulta lento nell’inserire o rimuovere gli elementi al centro del contenitore.
LinkedList: fornisce un ottimo accesso sequenziale con inserimenti ed eliminazioni poco costosi dal centro delle List. Risulta relativamente lenta negli accessi diretti. Supporta i metodi addFirst(), addLast(), getFirst(), getLast(), removeFirst() e removeLast() che gli permettono di essere usata come uno stack o una coda.
10.1 Set
Un Set contiene solo una istanza di ogni valore dell’oggetto. L’interfaccia Set non garantisce l’ordine degli oggetti inseriti. L’univocità degli elementi è stabilita mediante il metodo equals().
Classi che implementano l’interfaccia Set sono:
- HashSet: è utilizzato per Set che richiedono tempi di accesso più brevi. Per gli oggetti si definisce un metodo hashCode().
class Studente {
private int matricola;
private String cognome;
Studente(int matricola, String cognome) {
this.matricola = matricola;
this.cognome = cognome;
}
public boolean equals (Object o) {
return ((Studente)o).getMatricola() == matricola;
}
int getMatricola() {
return matricola;
}
public int hashCode() {
return new Integer(matricola).hashCode();
}
public String toString() {
return cognome;
}
}
import java.util.HashSet;
class Tester {
public static void main(String args[]) {
HashSet s = new HashSet();
s.add(new Studente(1, ”Bianchi”));
s.add(new Studente(2, ”Rossi”));
s.add(new Studente(1, ”Verde”));
System.out.println(s);
}
}
Output
[Bianchi, Rossi]- TreeSet: è un Set ordinato attraverso un albero. In tal modo si può estrarre una sequenza ordinata da un Set.
class Studente implements Comparable {
private int matricola;
private String cognome;
Studente(int matricola, String cognome) {
this.matricola = matricola;
this.cognome = cognome;
}
public int compareTo(Object o) {
return matricola == ((Studente)o).getMatricola();
}
int getMatricola() {
return matricola;
}
public String toString() {
return cognome;
}
}
import java.util.TreeSet;
class Tester {
public static void main(String args[]) {
TreeSet s = new TreeSet();
s.add(new Studente(1, ”Bianchi”));
s.add(new Studente(2, ”Rossi”));
s.add(new Studente(1, ”Verde”));
System.out.println(s);
}
Output
[Bianchi, Rossi]Pur accettando l’inserimento di valori duplicati, si può notare che quando il contenuto del Set viene visualizzato si vede che essi non sono stati considerati. I Set ordinati (di cui il TreeSet è l’unico accessibile) aggiungono funzionalità nuove, rispetto ai Set comuni, che permettono di gestire l’ordinamento degli elementi inseriti.
11 Map
L’interfaccia Map permette di accedere agli oggetti di un contenitore attraverso un altro oggetto.
A tale scopo abbiamo i seguenti metodi:
put(Object key, Object value): aggiunge un valore e lo associa con una chiave;
get(Object key): restituisce il valore corrispondente alla chiave;
containsKey(Object key), containsValue(Object value): verifica se Map contiene un valore o una chiave.
La libreria standard di Java include due tipi differenti di Map: HashMap e TreeMap.
Entrambe le classi hanno la stessa interfaccia ma si distinguono per efficienza.
- L’HashMap garantisce elevate prestazioni per la ricerca di una chiave perché è una implementazione basata sulla tabella hash. Infatti ogni oggetto Java può produrre un codice hash (di tipo int) attraverso il metodo hashCode() definito nella classe Object. HashMap utilizza tale codice per effettuare una ricerca efficiente sugli elementi. Il metodo hashCode() usa per default l’indirizzo dell’oggetto per poter generare il valore intero. Può quindi accadere che oggetti differenti per indirizzo, ma identici per valore, siano indicizzati in modo diverso.
public class ObjectHashCode {
public static void main(String[] args) {
System.out.println((new Object()).hashCode());
System.out.println((new Object()).hashCode());
}
}Per risolvere il problema si può sovrascrivere il metodo hashCode() per la classe di oggetti chiave da memorizzare in una Map. Questo è quello che avviene ad esempio per String o Integer.
Esempio di utilizzo dell’HashMap:
class Studente {
private int matricola;
private String cognome;
Studente(int matricola, String cognome) {
this.matricola = matricola;
this.cognome = cognome;
}
public boolean equals(Object o) {
return ((Studente)o).getMatricola() == matricola;
}
int getMatricola() {
return matricola;
}
public int hashCode() {
Integer i = new Integer(matricola);
return i.hashCode();
}
public String toString() {
return cognome;
}
}
class Counter {
private int i = 1;
Counter (int i) {
this.i = i;
}
public String toString() {
return Integer.toString(i);
}
}
// Semplice esempio di HashMap.
import java.util.*;
class Statistics {
public static void main(String[] args) {
HashMap hm = new HashMap();
hm.put(new Studente(1, "Bianchi"), new Counter(1));
hm.put(new Studente(2, "Rossi"), new Counter(2));
hm.put(new Studente(2, "Verde"), new Counter(3));
hm.put(new Studente(3, "Bianchi"), new Counter(4));
}
}
Output
{Bianchi = 1, Rossi = 3, Bianchi = 4}❗Attenzione: abbiamo aggiunto in hm due studenti con la stessa matricola. Dato che l’hashCode è stato realizzato prendendo in considerazione solo la matricola, questi due oggetti hanno lo stesso hashCode. L’HashMap in situazioni del genere aggiorna il valore associato a quella chiave, quindi non ignora il put scritto. Per il TreeMap funziona allo stesso modo: se la chiave è uguale ad un’altra chiave aggiorna il valore associato alla chiave
- TreeMap: le coppie chiave-valore sono ordinate (attraverso i metodi della interfaccia Comparable). TreeMap dispone di un metodo subMap() che restituisce una porzione dell’albero costruito per mantenere ordinati gli oggetti.
class Studente implements Comparable {
private int matricola;
private String cognome;
Studente(int matricola, String cognome) {
this.matricola = matricola;
this.cognome = cognome;
}
int getMatricola() {
return matricola;
}
public int compareTo(Object o) {
Studente s = (Studente)o;
Integer i = new Integer(s.matricola);
Integer m = new Integer(matricola);
return m.compareTo(i);
}
public String toString() {
return cognome;
}
}
// Semplice esempio di TreeMap.
import java.util.*;
class Statistics {
public static void main(String[] args) {
TreeMap tm = new TreeMap();
tm.put(new Studente(1, "Bianchi"), new Counter(1));
tm.put(new Studente(2, "Rossi"), new Counter(2));
tm.put(new Studente(2, "Verde"), new Counter(3));
tm.put(new Studente(3, "Bianchi"), new Counter(4));
}
}11.1 HashCode con più campi
In tutti gli esempi visti è stato realizzato l’hashCode utilizzando un solo campo, per utilizzare più campi per creare l’hashCode è possibile utilizzare Objects.hash(Object … values).
Under the hood, hash() inserisce gli oggetti in un Array e chiama Arrays.hashCode() su di loro.
Pertanto se passiamo un solo oggetto a Objects.hash, non dobbiamo aspettarci lo stesso risultato di chiamare Objects.hashcode() sull’oggetto.
11.2 Recuperare le entry di un Map
for (Map.Entry<TipoChiave, TipoValore> entry : NomeTreeMap.entrySet()) {
TipoChiave key = entry.getKey();
TipoValore valore = entry.getValue();
}